package primary.code05_Tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author Yudi Wang
 * @date 2021/7/12 13:11
 * <p>
 * 判断 完全二叉树 (宽/广度优先遍历)
 * 宽度优先遍历
 * 1 只有 右子树 则否
 * 2 遇到子树不全的节点,之后的节点均为叶子节点
 */
public class Code05_CompleteBinaryTree {

    /**
     * 判断 完全二叉树
     *
     * @param head
     * @return
     */
    private static boolean judgeCBT(Node head) {
        if (head == null) return true;
        Queue<Node> queue = new LinkedList<>();
        Node cur = head;
        queue.add(cur);
        boolean leftNodeFlag = false;//开始遇到叶节点
        while (!queue.isEmpty()) {
            cur = queue.poll();
            if (cur.right != null && cur.left == null) {
                return false;
            }
            // 注意下面if条件的次序
            if (leftNodeFlag && (cur.right != null || cur.left != null)) {
                return false;
            }
            if (cur.right == null || cur.left == null) {
                leftNodeFlag = true;
            }
            if (cur.left != null) {
                queue.add(cur.left);
            }
            if (cur.right != null) {
                queue.add(cur.right);
            }
        }
        return true;
    }

    private static boolean judgeCBTTest(Node root) {
        if (root == null) return true;
        boolean leaf = false;
        Queue<Node> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            Node cur = q.poll();
            if (cur.left == null && cur.right != null) {
                return false;
            }
            if (leaf & !(cur.left == null && cur.right == null)) {
                return false;
            }
            if (cur.left == null || cur.right == null) {
                leaf = true; // 下个访问的节点开始，放在最后一个if
            }
            if (cur.left != null) q.add(cur.left);
            if (cur.right != null) q.add(cur.right);
        }
        return true;
    }

    public static void main(String[] args) {
        Node head = new Node(4);
        head.left = new Node(3);
        head.right = new Node(8);
        head.left.left = new Node(2);
        head.left.right = new Node(4);
//        head.right.left = new Node(7);//注释则为非完全二叉树
        head.right.left = new Node(9);
        boolean res1 = judgeCBT(head);
        boolean res2 = judgeCBTTest(head);
        System.out.println(res1);
        System.out.println(res2);
    }
}
